package aa;

public class AA {

    public static void main(String[] args) {
        
        // Define o tamanho da parede
        final int tamanhoParede = 9999999;//(int)(1 + (Math.random() * 1000000));
        
        // Define a posicao da porta
        final int posicaoPorta = 0; //(int)(1 + (Math.random() * tamanhoParede))
        
        // Exibe onde a porte será posicionada
        System.out.println("Porta posicionada em: " + posicaoPorta);
        
        // Cria a parede
        final boolean[] parede = new boolean[tamanhoParede];
        
        // Adiciona a porta
        parede[posicaoPorta] = true;
        
        // Invoca o algoritmo para encontrar a porta
        final int portaEncontrada = encontrarPorta(parede);
        
        // Exibe o resultado
        System.out.println("Porta encontrada em: " + portaEncontrada);
        
    }
    
    private static int encontrarPorta(final boolean[] parede){
        
        int posicaoPorta = -1;
        
        // Define o centro da parede
        final int centro = (parede.length + 1) / 2;
        
        // Variavel para definir onde estou
        int ondeEstou = 0;
        
        for(int p = 1; posicaoPorta == -1; p++){
            
            // Andar até 2^p
            for(ondeEstou++; (ondeEstou + centro) < parede.length && ondeEstou <= Math.pow(2, p) && posicaoPorta == -1; ondeEstou++){
                if(parede[ondeEstou + centro]){
                    posicaoPorta = ondeEstou + centro;
                    break;
                }
            }
            
            // Andar até -(2^p)
            for(ondeEstou--; (ondeEstou + centro) >= 0 && ondeEstou >= -Math.pow(2, p) && posicaoPorta == -1; ondeEstou--){
                if(parede[ondeEstou + centro]){
                    posicaoPorta = ondeEstou + centro;
                    break;
                }
            }
            
        }
        
        return posicaoPorta;
        
    }
            
}

